package com.sourcetrip.algorithm.unionfind;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description: 并查集-按秩合并优化-路径分裂优化
 */
public class UnionFindWithQuickUnionV4 extends UnionFindWithQuickUnionV2 {
	/**
	 * 构建固定容量的并查集
	 * 默认初始 parents 的元素的根节点指向自身，这样表示每个元素都是独立的集合
	 *
	 * @param capacity 并查集的容量
	 */
	public UnionFindWithQuickUnionV4(int capacity) {
		super(capacity);
	}

	/**
	 * Path Splitting 算法
	 * 我的实现：在每一次循环由一步改为两步！
	 *
	 * @param v
	 * @return
	 */
	@Override
	protected int locate(int v) {
		int res = v;
		int grand = v;
		int son = v;

		while (parents[res] != res) {
			son = res;
			res = parents[res];
			//再判断一遍，步长由一步增大为两步
			if (parents[res] == res) {
				//将
				parents[son] = res;
				break;
			} else {
				grand = son;
				son = res;
				res = parents[res];
				parents[grand] = res;
			}
		}
		return res;
	}
}
